/*
============================================================================
 Name        : dd_bheap.c
 Author      : Jian (raphyer@hotmail.com)
 Version     :
 Copyright   : GPL
 Description : dd_bheap.c - source file
============================================================================
*/

/* INCLUDE FILES */
#include "dd_bheap.h"
#include "dd_vector.h"
#include "dd_log.h"


#define __DD_BHEAP_VEC_DEF_SIZE  30 

#define __pIndex(i)  (((i) -1) / 2) 
#define __lcIndex(p) (((p) + 1) * 2 - 1)
#define __rcIndex(p) (((p) + 1) * 2)



static void _swap(dd_bheap* heap, int index1, int index2) 
{
    if (heap->update_index) {
        heap->update_index(dd_vector_getfast(heap->vec, index1), index2) ;
        heap->update_index(dd_vector_getfast(heap->vec, index2), index1) ;
    }
    
    dd_vector_swap(heap->vec, index1, index2) ;
}

static void _check_down_to_top(dd_bheap* heap, int index) 
{
    int pIndex     = 0 ;
    int cmp_factor = (heap->type == EDDMaxHeap) ? -1 : 1 ;
    
    while(index > 0) {
        
        pIndex = __pIndex(index) ;
        
        if ( heap->compare(dd_vector_getfast(heap->vec, pIndex), dd_vector_getfast(heap->vec, index)) != cmp_factor)  
            break ;
        
        _swap(heap, index, pIndex) ;
        index = pIndex ;
    }
}

static void _check_top_to_down(dd_bheap* heap, int index) 
{
    int cindex     = 0 ;
    int cmp_factor = (heap->type == EDDMaxHeap) ? -1 : 1 ;
    
    while(__lcIndex(index) < dd_vector_count(heap->vec)) {
        
        cindex = __lcIndex(index) ;
        
        if (__rcIndex(index) < dd_vector_count(heap->vec) && 
            heap->compare(dd_vector_getfast(heap->vec, __rcIndex(index)), dd_vector_getfast(heap->vec, __lcIndex(index))) != cmp_factor ) 
            cindex = __rcIndex(index) ; 
        
        _swap(heap, cindex, index) ;
        index = cindex ;
    }
}


dd_bheap* dd_bheap_create(
    dd_bheap_type type,
    int (*compare)(const dd_bheap_value*, const dd_bheap_value*), 
    void (*update_index)(dd_bheap_value* , int),
    int (*index)(const dd_bheap_value*)
) 
{
    dd_bheap* heap;
    
    __DD_ASSERT_DEFENSE(compare, return NULL) ;
    
    heap               = (dd_bheap*)dd_malloc(sizeof(dd_bheap)) ;

    __DD_CHECK_MEM(heap, sizeof(dd_bheap), return NULL) ;
    
    heap->type         = type ;
    heap->vec          = dd_vector_create(__DD_BHEAP_VEC_DEF_SIZE) ;
    heap->compare      = compare ;
    heap->update_index = update_index ;
    heap->index        = index ;

    return heap ;
}


dd_bheap* dd_bheap_create_by(
    dd_bheap_type type,
    struct __dd_vector* vec,
    int (*compare)(const dd_bheap_value*, const dd_bheap_value*), 
    void (*update_index)(dd_bheap_value* , int),
    int (*index)(const dd_bheap_value*)
) 
{
    dd_bheap* heap ;
    int i ;
    int count ;

    __DD_ASSERT_DEFENSE(vec && compare, return NULL) ;
    
    heap               = (dd_bheap*)dd_malloc(sizeof(dd_bheap)) ;
    heap->type         = type ;
    heap->vec          = vec ;
    heap->compare      = compare ;
    heap->update_index = update_index ;
    heap->index        = index ;
    
    i     = 0 ;
    count = dd_vector_count(heap->vec) ;
    
    vec->count = 0 ;    /* Use the same vector, set the count = 0 to lie the vector'api that no data was in vector, but we know that it have the right data */
    
    for (i = 0; i < count; i++) {    
        dd_bheap_insert(heap, dd_vector_getfast(vec, i)) ;  
    }

    return heap ;
}

void dd_bheap_destroy(dd_bheap* heap) 
{
    __DD_ASSERT_DEFENSE(heap, return) ;
    
    if (heap->vec)
        dd_vector_destroy(heap->vec, NULL) ;
    
    dd_free(heap) ;
}


int dd_bheap_count(const dd_bheap* heap) 
{
    __DD_ASSERT_DEFENSE(heap, return 0) ;

    return dd_vector_count(heap->vec) ;
}


void dd_bheap_insert(dd_bheap* heap, dd_bheap_value* value) 
{
    __DD_ASSERT_DEFENSE(heap, return) ;
    
    if (heap->update_index)
        heap->update_index(value, dd_vector_count(heap->vec)) ;

    dd_vector_append(heap->vec, value) ;

    _check_down_to_top(heap, dd_vector_count(heap->vec) - 1) ;
}


dd_bheap_value* dd_bheap_delete(dd_bheap* heap) 
{
    dd_bheap_value* ret = NULL ;

    __DD_ASSERT_DEFENSE(heap && dd_vector_count(heap->vec) > 0, return NULL) ;

    ret = dd_vector_getfast(heap->vec, 0) ; 
    
    dd_vector_swap(heap->vec, 0, dd_vector_count(heap->vec) - 1) ;

    dd_vector_delete_by_index(heap->vec, dd_vector_count(heap->vec) - 1) ;
    
    _check_top_to_down(heap, 0) ;

    return ret ;
}


void dd_bheap_change(dd_bheap* heap, dd_bheap_value* value) 
{
    int index      = 0 ;
    int cmp_factor = 0 ;

    __DD_ASSERT_DEFENSE(heap, return) ;
    __DD_ASSERT_DEFENSE(heap->update_index && heap->index, return) ;
    
    index      = heap->index(value) ;
    cmp_factor = (heap->type == EDDMaxHeap) ? -1 : 1 ;

    if (index > 0) {
        if (heap->compare(dd_vector_getfast(heap->vec, __pIndex(index)), dd_vector_getfast(heap->vec, index)) == cmp_factor) 
            _check_down_to_top(heap, index) ;
    }

    if (__lcIndex(index) < dd_vector_count(heap->vec)) {
        if (heap->compare(dd_vector_getfast(heap->vec, index), dd_vector_getfast(heap->vec, __lcIndex(index))) == cmp_factor) 
            _check_top_to_down(heap, index) ;
    }
}


void dd_bheap_sort(
    dd_bheap_type type, 
    struct __dd_vector* vec,
    int (*compare)(const dd_bheap_value*, const dd_bheap_value*)
) 
{
    dd_bheap* heap = NULL;
    int i       = 0 ;
    int count   = 0;
    
    __DD_ASSERT_DEFENSE(vec && compare, return) ;
    
    count = dd_vector_count(vec) ;
    if (count == 0) return ;

    heap       = dd_bheap_create_by((type == EDDMaxHeap ? EDDMinHeap : EDDMaxHeap), vec, compare, NULL, NULL) ;
    
    for (i = 0; i < count ; i++) {
        dd_bheap_value* val = dd_bheap_delete(heap) ;
        dd_vector_setfast(heap->vec, count - i - 1, val) ;
    }

    heap->vec->count = count ;
    
    heap->vec = NULL ;   /* Don't free the vector */

    dd_bheap_destroy(heap) ; 
}


#ifdef __DD_TEST

typedef struct __test_value {
    int val ;
    int index ;
}test_value;

static test_value* _ut_create_test_value(int val)
{
    test_value* tval = (test_value*)dd_malloc(sizeof(test_value)) ;
    tval->index      = -1 ;
    tval->val        = val ;
    return tval ;
}

static void _ut_destroy_test_value(void* tval)
{
    dd_free(tval) ;
}

static int _test_compare(const dd_bheap_value* v1, const dd_bheap_value* v2) 
{
    test_value* val1 = (test_value*)v1 ;
    test_value* val2 = (test_value*)v1 ;

    if (val1->val < val2->val) return -1 ;
    
    if (val1->val > val2->val) return 1 ;
    
    return 0 ;
}

static void _test_update_index(dd_bheap_value* value, int index) 
{
    test_value* val = (test_value*)value ;
    val->index = index ;
}


static int _test_index(const dd_bheap_value* value) 
{
    test_value* val = (test_value*)value ;
    return val->index ;
}


#define __TEST_TIMES            (1000 + 1)
#define __TEST_INIT_VEC_COUNT   (__TEST_TIMES / 2)
#define __TEST_SORT_TIMES       (__TEST_TIMES + __TEST_INIT_VEC_COUNT)

#define __TEST_MAX       0
#define __TEST_MIN       1
#define __TEST_MAX_BYVEC 2
#define __TEST_MIN_BYVEC 3 


static DD_BOOL _ut_check_node(const dd_bheap* heap, int index) 
{
    dd_vector* vec    = heap->vec ;
    int cmp_factor = (heap->type == EDDMaxHeap) ? -1 : 1 ;
    
    if (__lcIndex(index) < dd_vector_count(vec)) {
        if (heap->compare(dd_vector_get(vec, index), dd_vector_get(vec, __lcIndex(index))) == cmp_factor) {
            dd_log_error("_ut_check_node ERROR, the LEFT_CHILD index not match the check \n") ;
            return DD_FALSE ;
        }

        if (!_ut_check_node(heap, __lcIndex(index)))
            return DD_FALSE ;
    }

    if (__rcIndex(index) < dd_vector_count(vec)) {
        if (heap->compare(dd_vector_get(vec, index), dd_vector_get(vec, __rcIndex(index))) == cmp_factor) {
            dd_log_error("_ut_check_node ERROR, the RIGHT_CHILD index not match the check \n") ;
            return DD_FALSE ;
        }

        if (!_ut_check_node(heap, __rcIndex(index)))
            return DD_FALSE ;
    }
     
    return DD_TRUE ;
}


static DD_BOOL _ut_check_bheap(const dd_bheap* heap)
{
    return _ut_check_node(heap, 0) ;
}


DD_BOOL dd_bheap_test() 
{
    dd_bheap* test_heap = NULL ;
    dd_vector* test_vec = NULL ;
    dd_vector* save_vec = dd_vector_create(__TEST_TIMES + __TEST_INIT_VEC_COUNT) ;

    int i = 0 ;
    int save_vec_count = 0 ;

    int test_phase = __TEST_MAX ;

    srand((DD_UINT)time(0)) ;

    while(test_phase <= __TEST_MIN_BYVEC) {
        
        switch (test_phase) {
        case __TEST_MAX:
            test_heap = dd_bheap_create(EDDMaxHeap, _test_compare, _test_update_index, _test_index) ;
            break ;

        case __TEST_MIN:
            test_heap = dd_bheap_create(EDDMinHeap, _test_compare, _test_update_index, _test_index) ;
            break ;

        case __TEST_MAX_BYVEC:
            test_vec  = dd_vector_create(__TEST_INIT_VEC_COUNT) ;
            i = 0 ;
            for (;i < __TEST_INIT_VEC_COUNT;i++) {
                test_value* k = _ut_create_test_value(rand());
                dd_vector_append(test_vec, k) ;
                dd_vector_append(save_vec, k) ;
            }
            test_heap = dd_bheap_create_by(EDDMaxHeap, test_vec, _test_compare, _test_update_index, _test_index) ;
            break ;

        case __TEST_MIN_BYVEC:
            test_vec  = dd_vector_create(__TEST_INIT_VEC_COUNT) ;
            i = 0 ;
            for (;i < __TEST_INIT_VEC_COUNT;i++) {
                test_value* k = _ut_create_test_value(rand());
                dd_vector_append(test_vec, k) ;
                dd_vector_append(save_vec, k) ;
            }
            test_heap = dd_bheap_create_by(EDDMinHeap, test_vec, _test_compare, _test_update_index, _test_index) ;
            break ;
        }
        
        i = 0 ;
        for ( ; i < __TEST_TIMES; i++) {
            test_value* k = _ut_create_test_value(rand());
            dd_bheap_insert(test_heap, k) ;
            dd_vector_append(save_vec, k) ;
            
            if (!_ut_check_bheap(test_heap)) {
                dd_log_error("dd_bheap_insert ERROR\n") ;
                return DD_FALSE ;
            }
        }

        i = 0 ;
        for ( ; i < __TEST_TIMES / 2; i++) {
            
            test_value* k = (test_value*)dd_vector_get(save_vec, i) ;
            k->val = rand() ;
            dd_bheap_change(test_heap, k) ;
            
            if (!_ut_check_bheap(test_heap)) {
                dd_log_error("dd_bheap_change ERROR\n") ;
                return DD_FALSE ;
            }
        }

        while (dd_vector_count(save_vec) > 0) {

            test_value* k = (test_value*)dd_bheap_delete(test_heap) ;

            if (!k) {
                dd_log_error("dd_bheap_delete ERROR 1\n") ;
                return DD_FALSE ;
            }
            
            if (!dd_vector_delete(save_vec, k)) {
                dd_log_error("dd_bheap_delete ERROR 2\n") ;
                return DD_FALSE ;
            }

            if (!_ut_check_bheap(test_heap)) {
                dd_log_error("dd_bheap_delete ERROR 3\n") ;
                return DD_FALSE ;
            }

            _ut_destroy_test_value(k) ;
        }

        if (dd_bheap_count(test_heap) != 0) {
            dd_log_error("dd_bheap_delete ERROR 4 and dd_bheap_count = %d\n", dd_bheap_count(test_heap)) ;
            return DD_FALSE ;
        }
        
        test_phase++ ;
        dd_bheap_destroy(test_heap) ;
        test_vec = NULL ;
        dd_vector_reset(save_vec, _ut_destroy_test_value) ;
    }
    
    i = 0 ;
    dd_vector_reset(save_vec, _ut_destroy_test_value) ;
    for (; i < __TEST_SORT_TIMES; i++) {
        test_value* k = _ut_create_test_value(rand());
        dd_vector_append(save_vec, k) ;    
    }

    dd_bheap_sort(EDDMinHeap, save_vec, _test_compare) ;

    if (dd_vector_count(save_vec) != __TEST_SORT_TIMES) {
        dd_log_error("dd_bheap_sort ERROR 1\n") ;
        return DD_FALSE ;
    }

    i = 0 ;
    for (; i < __TEST_SORT_TIMES - 1; i++) {
        test_value* val1 = (test_value*)dd_vector_get(save_vec, i) ;
        test_value* val2 = (test_value*)dd_vector_get(save_vec, i+1) ;
        if (_test_compare(val1, val2) == 1) {
            dd_log_error("dd_bheap_sort ERROR 2\n") ;
            return DD_FALSE ;
        }
    }

    return DD_TRUE ;
}

#endif	/* __DD_TEST */


/* End of File */
